import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * 统计前K个高频单词
 * User: xwl
 * Date: 2023-06-03
 * Time: 19:36
 */
public class Test3 {
    public List<String> topKFrequent(String[] words, int k) {
        // 遍历数组，统计每个单词出现的次数
        Map<String, Integer> hashMap = new HashMap<>();
        for (String s : words) {
            if (hashMap.get(s) == null) {
                hashMap.put(s,1);
            }else {
                hashMap.put(s, hashMap.get(s) + 1);
            }
        }
        // 建立小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(
                k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        }
        );
        // 遍历hashMap
        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                // 比较
                Map.Entry<String, Integer> top = minHeap.peek();
                if (entry.getValue().compareTo(top.getValue()) > 0) {
                    // 较大的值直接放到一个新的存储空间
                    minHeap.poll();
                    minHeap.offer(entry);
                } else {
                    if (entry.getValue().compareTo(top.getValue()) == 0) {
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        // 建立List
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String key = minHeap.poll().getKey();
            ret.add(key);
        }
        Collections.reverse(ret);
        // 返回
        return ret;
    }

}
